class Solution132 {
    public int minCut(String s) {
        int n = s.length() ;
        char[] arr = s.toCharArray() ;
        // f[i][j] : [i , j] 区间的是否是一个回文
        boolean[][] f = new boolean[n][n] ;
        // g[i] : [0 , i] 以i结尾时 , 最小分割数
        int[] g = new int[n] ;
        // 如果 [0 , i] 是 回文, 那么g[i] 就是0 ,
        // 如果 [0 , i] 不是回文 , g[i] = g[i-1] + 1 , i-1的情况加上 第i个
        for(int i=n-1 ; i >= 0 ; i --){
            for(int j=i ; j < n ; j ++){
                if(arr[i] == arr[j]){
                    if(i == j || i+1 == j){
                        f[i][j] = true ;
                    }else{
                        f[i][j] = f[i+1][j-1] ;
                    }
                }
            }
        }

        for(int i=0 ; i < n ; i ++){
            g[i] = Integer.MAX_VALUE ;
            if(f[0][i] == true){
                g[i] = 0 ;
            }else{
                for(int j=i ; j >= 0 ; j --){
                    if(f[j][i] == true){
                        g[i] = Math.min(g[i] , g[j-1] + 1) ;
                    }
                }
            }
        }
        return g[n-1] ;
    }
}